package algorithm.middle;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: EqualSubstring1208
 * @description: 给你两个长度相同的字符串，s 和 t。
 *
 * 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
 *
 * 用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
 *
 * 如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
 *
 * 如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/get-equal-substrings-within-budget
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/517:11
 * @since V1.0
 */
public class EqualSubstring1208 {

    public static void main(String[] args) {

        equalSubstring("abcd","cdef",3);
    }

    //双指针，滑动窗口
    public static int equalSubstring(String s, String t, int maxCost) {
        char[] sarr = s.toCharArray();
        char[] tarr = t.toCharArray();
        int left = 0;
        int right = 0;
        int current = 0;
        int maxsize = 0;
        while (right<sarr.length){
            current = current + Math.abs(tarr[right]-sarr[right]);
            while(current>maxCost){
                current = current - Math.abs(tarr[left]-sarr[left]);
                left++;
            }
            maxsize = Math.max(maxsize,right-left+1);
            right++;
        }
        return maxsize;
    }

    //提前把两数组对位的差值存起来
    public int 官方题解(String s, String t, int maxCost) {
        int n = s.length();
        int[] diff = new int[n];
        for (int i = 0; i < n; i++) {
            diff[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int maxLength = 0;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += diff[end];
            while (sum > maxCost) {
                sum -= diff[start];
                start++;
            }
            maxLength = Math.max(maxLength, end - start + 1);
            end++;
        }
        return maxLength;
    }

}
